home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / circuits / irsim-ca.2 / irsim-ca / irsim-cap-9.2 / src / irsim / mem.c < prev    next >
C/C++ Source or Header  |  1993-01-15  |  15KB  |  601 lines
  1. /* 
  2.  *     ********************************************************************* 
  3.  *     * Copyright (C) 1988, 1990 Stanford University.                     * 
  4.  *     * Permission to use, copy, modify, and distribute this              * 
  5.  *     * software and its documentation for any purpose and without        * 
  6.  *     * fee is hereby granted, provided that the above copyright          * 
  7.  *     * notice appear in all copies.  Stanford University                 * 
  8.  *     * makes no representations about the suitability of this            * 
  9.  *     * software for any purpose.  It is provided "as is" without         * 
  10.  *     * express or implied warranty.  Export of this software outside     * 
  11.  *     * of the United States of America may require an export license.    * 
  12.  *     ********************************************************************* 
  13.  */
  14.  
  15. /*
  16.  *   This is a very low overhead storage allocator for managing many
  17.  * "small" objects.
  18.  *
  19.  *   The allocator recognizes 2 different types of objects: (1) small
  20.  * fixed size objects, and (2) large or variable size objects.
  21.  *
  22.  *   Variable size objects are allocated on demand, using a next-fit
  23.  * algorithm.  The same is used for large objects.
  24.  *
  25.  *   When a small fixed size object is requested, the allocator will
  26.  * pre-allocate as many such objects as will fit in one page (4Kbytes in-
  27.  * this implementation).  The unused objects are put in a free list for
  28.  * quick access later on.  A separate free list for every object size is
  29.  * maintained.  When such an object is freed, it is simply put back in
  30.  * its respective free list (small objects don't migrate from one free
  31.  * list to another).
  32.  *
  33.  *   All objects returned by Malloc are word aligned: a word is defined to
  34.  * be the smallest size integer into which an address can be cast.  All
  35.  * requests are rounded to a multiple of words (as defined above).
  36.  *
  37.  *   The allocator does not "remember" the size of fixed-size objects. Keeping
  38.  * this information is left to the user.  It does however, remeber the size of
  39.  * objects allocated using Valloc.
  40.  *
  41.  *   The allocator provides the following interfaces:
  42.  *    1) Falloc( nbytes )
  43.  *        returns a pointer to nbytes of storage. For fixed size objects.
  44.  *    2) Valloc( nbytes )
  45.  *        returns a pointer to nbytes of storage. For variable size objects.
  46.  *    3) MallocList( size )
  47.  *        returns a linked list of 'size' bytes objects.
  48.  *    4) Ffree( ptr, nbytes )
  49.  *        deallocate the fixed size object of 'nbytes' pointed to by 'ptr'.
  50.  *    4) Vfree( ptr )
  51.  *        deallocate the variable object of 'nbytes' pointed to by 'ptr'.
  52.  *
  53.  *    The argument to Ffree can be any any object obtained from Falloc, or
  54.  * any one of the elements obtained from MallocList.
  55.  */
  56.  
  57.  
  58.  
  59. #include <sys/types.h>
  60. #ifndef SYS_V
  61. #    include <sys/time.h>
  62. #    include <sys/resource.h>
  63. #endif
  64. #include <stdio.h>
  65. #include "defs.h"
  66.  
  67.  
  68.     /* number of bytes in a word */
  69. #define    WORDSIZE        ( sizeof( Object ) )
  70.  
  71.     /* round x to nearest z (ceiling function) */
  72. #define    ROUND( x, z )        ( ((x) + (z) - 1) / (z) )
  73.  
  74.     /* convert size in bytes to nearest number of words */
  75. #define    NWORDS( x )        ROUND( x, WORDSIZE )
  76.  
  77.     /* number of bytes/words per page */
  78. #define    DATABYTES        4096
  79. #define    DATAWORDS        ( DATABYTES / WORDSIZE )
  80.  
  81.     /* objects larger than this many words are considered large */
  82. #define    BIG_OBJ            40
  83.  
  84. #define    NBINS            (BIG_OBJ + 1)
  85.  
  86.  
  87. typedef union Object *Pointer;
  88.  
  89. typedef union Object        /* Basic data object (i.e. `machine word') */
  90.   {
  91.     Pointer  ptr;
  92.     int      num;
  93.     int      align[1];
  94.   } Object;
  95.  
  96.  
  97.  
  98.     /* export this definition for the user's sake */
  99. public typedef union MElem
  100.   {
  101.     union MElem  *next;        /* points to next element in linked list */
  102.     int          align[1];    /* dummy used to force word alignment */
  103.   } *MList;
  104.  
  105.  
  106. typedef struct
  107.   {
  108.     Pointer  free1;        /* Lists of free objects of this size */
  109.     Pointer  free2;
  110.   } Bucket;
  111.  
  112.  
  113. private    Bucket  bucket[NBINS];        /* free list hash table */
  114.  
  115.  
  116.     /* External definitions */
  117. extern    char      *sbrk();
  118. extern          etext;
  119. extern    int      setrlimit(), getrlimit();
  120. extern    unsigned  sleep();
  121.  
  122.  
  123. #define    SBRK_FAIL        ( (char *) -1 )
  124. #define    MAXTRIES        5
  125.  
  126. #define    PAGE_SIZE        1024            /* for alignment */
  127. #define    PAGE_MASK        ( PAGE_SIZE - 1 )
  128.  
  129. #define    FPRINTF            (void) fprintf
  130.  
  131. /*
  132.  * Interface to the system's sbrk call.  If sbrk fails, try to determine
  133.  * what's happening and attempt to solve it.  If all fails return NULL.
  134.  */
  135.  
  136. #ifdef SYS_V
  137.  
  138. private Pointer GetMoreCore( npages )
  139.   int  npages;
  140.   {
  141.     char  *ret;
  142.     int   cursize, newsize, nbytes;
  143.     int   tries, inc;
  144.     long  lim;
  145.  
  146.     cursize = (int) sbrk( 0 );            /* align on 1K boundary */
  147.     inc = PAGE_SIZE - (cursize & PAGE_MASK) & PAGE_MASK;
  148.  
  149.     nbytes = npages * DATABYTES + inc;
  150.  
  151.     ret = sbrk( nbytes );
  152.     if( ret != SBRK_FAIL )
  153.     return( (Pointer) ret );
  154.  
  155.     newsize = cursize + nbytes;
  156.     lim = ulimit( 3, 0 );
  157.  
  158.     ret = SBRK_FAIL;
  159.  
  160.     if( newsize <= lim )
  161.       {
  162.     for( tries = 0; tries < MAXTRIES and ret == SBRK_FAIL; tries++ )
  163.       {
  164.         if( tries == 0 )
  165.           {
  166.         FPRINTF( stderr, "*** MEMORY WARNING ***\n" );
  167.         FPRINTF( stderr, "Current data size: %d (%dK)\n", cursize,
  168.           ROUND( cursize, 1024 ));
  169.         FPRINTF( stderr, "New data size = %d (%dK)\n", newsize,
  170.           ROUND( newsize, 1024 ) );
  171.         FPRINTF( stderr, "Hard limit = %d (%dK)\n", lim,
  172.           ROUND( lim, 1024 ));
  173.           }
  174.         FPRINTF( stderr, "I seem to be short on swap space\n" );
  175.         FPRINTF( stderr, "Will sleep for 15 seconds and try again\n");
  176.         (void) sleep( 15 );
  177.         ret = sbrk( nbytes );
  178.       }
  179.       }
  180.  
  181.     return( ( ret == SBRK_FAIL ) ? (Pointer) NULL : (Pointer) ret );
  182.   }
  183.  
  184. #else        /* BSD */
  185.  
  186. #ifdef host_mips            /* kludge for mips based systems */
  187. #    define    heap_start    (char *) 0x10000000
  188. #else
  189. #    define    heap_start    (char *) &etext
  190. #endif
  191.  
  192. private Pointer GetMoreCore( npages )
  193.   int  npages;
  194.   {
  195.     char           *ret;
  196.     int            cursize, newsize, nbytes;
  197.     int            tries, inc;
  198.     struct rlimit  lim;
  199.     
  200.     cursize = (int) sbrk( 0 );            /* align on 1K boundary */
  201.     inc = PAGE_SIZE - (cursize & PAGE_MASK) & PAGE_MASK;
  202.  
  203.     nbytes = npages * DATABYTES + inc;
  204.  
  205.     ret = sbrk( nbytes );
  206.     if( ret != SBRK_FAIL )
  207.     return( (Pointer) ret );
  208.  
  209.     cursize -= (int) heap_start;
  210.     newsize = cursize + nbytes;
  211.     (void) getrlimit( RLIMIT_DATA, &lim );
  212.  
  213.     if( newsize > lim.rlim_max )
  214.       {
  215.     FPRINTF( stderr, "Memory Error: Hard limit exceeded %d\n",
  216.       ROUND( lim.rlim_max, 1024 ) );
  217.     return( (Pointer) NULL );
  218.       }
  219.  
  220.     ret = SBRK_FAIL;
  221.     for( tries = 0; tries < MAXTRIES and ret == SBRK_FAIL; tries++ )
  222.       {
  223.     if( newsize < lim.rlim_cur )
  224.       {
  225.         if( tries == 0 )
  226.           {
  227.         FPRINTF( stderr, "*** MEMORY WARNING ***\n" );
  228.         FPRINTF( stderr, "Current data size: %d (%dK)\n", cursize,
  229.           ROUND( cursize, 1024 ));
  230.         FPRINTF( stderr, "New data size = %d (%dK)\n", newsize,
  231.           ROUND( newsize, 1024 ) );
  232.         FPRINTF( stderr, "Soft limit = %d (%dK)\n", lim.rlim_cur,
  233.           ROUND( lim.rlim_cur, 1024 ));
  234.         FPRINTF( stderr, "Hard limit = %d (%dK)\n", lim.rlim_max,
  235.           ROUND( lim.rlim_max, 1024 ));
  236.           }
  237.         FPRINTF( stderr, "I seem to be short on swap space\n" );
  238.         FPRINTF( stderr, "Will sleep for 15 seconds and try again\n");
  239.         (void) sleep( 15 );
  240.       }
  241.     else if( newsize < lim.rlim_max )
  242.       {
  243.         int  softlim = lim.rlim_cur;
  244.  
  245.         FPRINTF( stderr, "MEMORY WARNING: Soft limit exceeded\n" );
  246.         lim.rlim_cur = lim.rlim_max;
  247.         if( setrlimit( RLIMIT_DATA, &lim ) == 0 )
  248.           {
  249.         FPRINTF( stderr, 
  250.           " => Soft limit increased from %d (%dK) to %d (%d)\n",
  251.           softlim, ROUND( softlim, 1024 ),
  252.           lim.rlim_max, ROUND( lim.rlim_max, 1024 ) );
  253.           }
  254.         else
  255.           {
  256.         FPRINTF( stderr,
  257.           " => Can NOT increase Soft limit [%d (%dK)] to %d (%d)\n",
  258.           softlim, ROUND( softlim, 1024 ),
  259.           lim.rlim_max, ROUND( lim.rlim_max, 1024 ) );
  260.         FPRINTF( stderr, "I Will try again in 15 seconds\n" );
  261.         (void) sleep( 15 );
  262.           }
  263.       }
  264.     ret = sbrk( nbytes );
  265.       }
  266.  
  267.     return( ( ret == SBRK_FAIL ) ? (Pointer) NULL : (Pointer) ret );
  268.   }
  269.  
  270. #endif SYS_V
  271.  
  272.  
  273. /*
  274.  * Get nPages contiguous pages.  Make sure new pages are aligned on system
  275.  * page boundaries.
  276.  * If 'size' is <> 0, the elements in the page(s) are linked into a list.
  277.  */
  278. private Pointer GetPage( nPages, size, no_mem_exit )
  279.   int  nPages;
  280.   int  size;
  281.   int  no_mem_exit;
  282.   {
  283.     Pointer     pg;
  284.     int         inc;
  285.  
  286.     pg = GetMoreCore( nPages );
  287.  
  288.     if( pg == NULL )
  289.       {
  290.     if( no_mem_exit == 0 )
  291.         return( pg );
  292.     FPRINTF( stderr, "Out of memory.\n" );
  293.     exit( 1 );
  294.       }
  295.  
  296.     if( size != 0 )        /* Initialize the new page */
  297.       {
  298.     register Pointer  p, page;
  299.     register int      n, np, nwords;
  300.  
  301.     inc = DATAWORDS / size;
  302.     nwords = size;
  303.     page = pg;
  304.     np = nPages;
  305.     while( np-- > 0 )
  306.       {
  307.         n = inc;
  308.         for( p = page; --n > 0; p->ptr = p + nwords, p += nwords );
  309.         p->ptr = (np == 0) ? NULL : (page += DATAWORDS);
  310.       }
  311.       }
  312.     return( pg );
  313.   }
  314.  
  315.  
  316.         /* forward references */
  317. private    MList    MallocBigList();
  318.     char     *Valloc();
  319.     void     Ffree(), Vfree();
  320.  
  321.  
  322. public char *Falloc( nbytes, no_mem_exit )
  323.   int  nbytes;
  324.   int  no_mem_exit;
  325.   {
  326.     register Bucket   *bin;
  327.     register Pointer  p;
  328.     register int      nwords;
  329.  
  330.     if( nbytes <= 0 )            /* ubiquitous check */
  331.     return( NULL );
  332.  
  333.     nwords = NWORDS( nbytes );
  334.     if( nwords >= NBINS )
  335.     return( Valloc( nbytes, no_mem_exit ) );
  336.  
  337.     bin = &(bucket[nwords]);
  338.     if( (p = bin->free1) != NULL )
  339.       {
  340.     if( (bin->free1 = p->ptr) == NULL )
  341.       {
  342.         bin->free1 = bin->free2;
  343.         bin->free2 = NULL;
  344.       }
  345.       }
  346.     else
  347.       {
  348.     int  n;
  349.  
  350.     p = GetPage( 1, nwords, no_mem_exit );
  351.     if( p == NULL )            /* Out of memory */
  352.         return( NULL );
  353.  
  354.     n = nwords * ((DATAWORDS / nwords) / 2);
  355.     bin->free1 = p->ptr;
  356.     bin->free2 = p + n;
  357.     p[n - nwords].ptr = NULL;
  358.       }
  359.     return( (char *) p );
  360.   }
  361.  
  362.  
  363. public void Ffree( p, nbytes )
  364.   Pointer  p;
  365.   int      nbytes;
  366.   {
  367.     register int   nwords;
  368.  
  369.     if( p == NULL or nbytes <= 0 )    /* sanity ? */
  370.     return;
  371.  
  372.     nwords = NWORDS( nbytes );
  373.     if( nwords >= NBINS  )        /* big block */
  374.     Vfree( p );
  375.     else                /* return to its corresponding bin */
  376.       {
  377.     p->ptr = bucket[nwords].free1;
  378.     bucket[nwords].free1 = p;
  379.       }
  380.   }
  381.  
  382. /*
  383.  * Return a linked list of elements, each 'nbytes' long in size.
  384.  */
  385. public MList MallocList( nbytes, no_mem_exit )
  386.   int  nbytes;
  387.   int  no_mem_exit;
  388.   {
  389.     register Pointer  p;
  390.     register int      nwords, n;
  391.     register Bucket   *bin;
  392.  
  393.     if( nbytes <= 0 )
  394.     return( NULL );
  395.  
  396.     nwords = NWORDS( nbytes );
  397.     if( nwords >= NBINS )
  398.     return( MallocBigList( nbytes, no_mem_exit ) );
  399.  
  400.     bin = &(bucket[nwords]);
  401.     if( (p = bin->free1) != NULL )
  402.       {
  403.     bin->free1 = bin->free2;
  404.     bin->free2 = NULL;
  405.       }
  406.     else
  407.       {
  408.     p = GetPage( 1, nwords, no_mem_exit );
  409.     if( p == NULL )            /* Out of memory */
  410.         return( NULL );
  411.  
  412.     n = nwords * ((DATAWORDS / nwords) / 2);
  413.     bin->free1 = p + n;        /* save 2nd half of the page */
  414.     bin->free2 = NULL;
  415.     p[n - nwords].ptr = NULL;
  416.       }
  417.  
  418.     return( (MList) p );
  419.   }
  420.  
  421.  
  422. /*
  423.  * Handle the large (infrequent) case.
  424.  */
  425. private MList MallocBigList( nbytes, no_mem_exit )
  426.   int  nbytes;
  427.   int  no_mem_exit;
  428.   {
  429.     int      nelem;
  430.     Pointer  head, tail;
  431.  
  432.     nelem = ( nbytes < 2 * DATABYTES ) ? DATABYTES / nbytes : 2;
  433.     head = tail = (Pointer) Valloc( nbytes, no_mem_exit );
  434.     if( head == NULL )
  435.     return( NULL );
  436.  
  437.     while( --nelem > 0 )
  438.       {
  439.     tail->ptr = (Pointer) Valloc( nbytes, no_mem_exit );
  440.     if( tail->ptr == NULL )
  441.       {
  442.         while( head != NULL )
  443.           {                /* free everything already Malloc`d */
  444.         tail = head->ptr;
  445.         Vfree( head );
  446.         head = tail;
  447.           }
  448.         return( NULL );
  449.       }
  450.     tail = tail->ptr;
  451.       }
  452.     tail->ptr = NULL;
  453.     return( (MList) head );
  454.   }
  455.  
  456.  
  457.  
  458. /*
  459.  * Next-fit storage allocation for variable (infrequent) size objects.
  460.  * Algorithm and variable names from Knuth V1, p 437.  See Exercise 2.5.6.
  461.  */
  462. private    Object    avail[2];        /* dummy header that points to first
  463.                      * free element.  Free list is kept
  464.                      * in address order */
  465. private    Pointer   rover = avail;    /* pointer into the free list */
  466.  
  467.  
  468. #define    NEXT( blk )    ( (blk)->ptr )        /* next block in free list */
  469. #define    SIZE( blk )    ( blk[1].num )        /* words available in block */
  470.  
  471.  
  472. /*
  473.  * Add the block pointed to by 'ptr' to the free list.
  474.  */
  475. public void Vfree( ptr )
  476.   Pointer  ptr;
  477.   {
  478.     register Pointer  p, q, r;
  479.     register int      nwords;
  480.  
  481.     if( ptr == NULL )
  482.     return;
  483.  
  484.     ptr--;
  485.     nwords = ptr->num;
  486.     if( nwords <= 0 )
  487.     return;
  488.  
  489.     q = avail;
  490.     r = ptr;
  491.     p = NEXT( q );
  492.  
  493.     while( (p != NULL) and (p < r) )    /* search for the right place */
  494.       {
  495.     q = p;
  496.     p = NEXT( p );
  497.       }
  498.     /* this is where it should go */
  499.     /* note: since NULL = 0, if p = NULL, p != r + nwords */
  500.  
  501.     if( p == r + nwords )        /* new block abuts p, consolidate */
  502.       {
  503.     nwords += SIZE( p );
  504.     NEXT( r ) = NEXT( p );
  505.       }
  506.     else                /* does not abut, just connect */
  507.       {
  508.     NEXT( r ) = p;
  509.       }
  510.  
  511.     if( r == q + SIZE( q ) )        /* new block abuts q, consolidate */
  512.       {
  513.     SIZE( q ) += nwords;
  514.     NEXT( q ) = NEXT( r );
  515.       }
  516.     else                /* does not abut, just connect */
  517.       {
  518.     NEXT( q ) = r;
  519.     SIZE( r ) = nwords;
  520.       }
  521.     rover = q;            /* start searching here next time */
  522.   }
  523.  
  524.  
  525. /*
  526.  * Return a pointer to (at least) n bytes of storage.
  527.  */
  528. public char *Valloc( nbytes, no_mem_exit )
  529.   int  nbytes;
  530.   int  no_mem_exit;
  531.   {
  532.     register Pointer  p, q;
  533.     register int      nwords;
  534.     int               firstTime;
  535.  
  536.     if( nbytes <= 0 )            /* ubiquitous check */
  537.     return( NULL );
  538.  
  539.     nwords = (NWORDS( nbytes ) + 2) & ~1;
  540.  
  541.   Start :
  542.     if( (q = rover) == NULL )
  543.       {
  544.     q = rover = avail;
  545.     firstTime = 0;
  546.       }
  547.     else
  548.     firstTime = 1;
  549.  
  550.   again:
  551.     p = NEXT( q );
  552.     while( p != NULL )            /* search for a block large enough */
  553.       {
  554.     if( SIZE( p ) >= nwords )
  555.         goto found;
  556.     q = p;
  557.     p = NEXT( p );
  558.       }
  559.  
  560.     if( firstTime )
  561.       {
  562.     q = avail;            /* first time, one more chance */
  563.     firstTime = 0;
  564.     goto again;
  565.       }
  566.  
  567.       {            /* fall through: out of memory, get some more */
  568.     int      nPages;
  569.     Pointer  pg;
  570.  
  571.     nPages = 2 * (ROUND( nwords, DATAWORDS ));
  572.     pg = GetPage( nPages, 0, no_mem_exit );
  573.     if( pg == NULL )
  574.         return( NULL );
  575.  
  576.     pg->num =  nPages * DATAWORDS;
  577.     Vfree( pg + 1 );
  578.     goto Start;        /* try again */
  579.       }
  580.  
  581.   found :
  582.     if( SIZE( p ) == nwords )        /* exact match. remove block */
  583.       {
  584.     NEXT( q ) = NEXT( p );
  585.       }
  586.     else    /* SIZE( p ) > nwords => too large. take part of it */
  587.       {
  588.     register Pointer  r;
  589.  
  590.     r = p + nwords;             /* remaining free area */
  591.     NEXT( q ) = r;
  592.     NEXT( r ) = NEXT( p );
  593.     SIZE( r ) = SIZE( p ) - nwords;
  594.       }
  595.     rover = q;            /* start looking here next time */
  596.  
  597.     p->num = nwords;
  598.     p++;
  599.     return( (char *) p );
  600.   }
  601.